Cryptography is concerned with the alteration of messages to make them unintelligible to anyone except the intended recipient. The original message, M, also referred to as the plaintext, is represented by a finite string of symbols from a given alphabet, S. An encryption procedure codes the message using a transformation, E, that depends on a set of parameters, K, called the key. The result is an encrypted ciphertext EQU C=E(M;K)
The encrypted ciphertext is meaningless to an unintended observer. In a symmetric cryptosystem, the recipient of the ciphertext retrieves the original message by using the same key as the sender and employing a decryption transformation, D: EQU D(E(M;K);K)=M.
Therefore, if the message is to be successfully interpreted, the same key must be shared by both the sender and recipient of the message.
In the past, cryptography was used primarily within the military, intelligence, and diplomatic communities. With the increased speed and facility of data transfer provided by modern computer systems and information superhighways, cryptographic applications have begun to appear in banking, administration, computer networking, and counter-narcotics activities.
The emergence of new cryptographic concerns in non-traditional areas has led to the development of several iterated cryptosystems. An iterated cryptosystem relies upon the repeated application of weak functions to produce cryptographically strong results. Specifically, many encryption methods are not strong enough to produce secure, strong results. However, when these methods are applied multiple times in series very good results may be achieved.
The theory behind iterated procedures is best demonstrated with reference to shuffling a deck of cards. Although the first shuffle of an ordered deck of cards only mixes the cards to a limited extent, subsequent shuffling of the same deck produces a well mixed deck of cards.
Currently the most popular iterated cryptosystem is the Data Encryption Standard (DES). The DES was adopted by the National Bureau of Standards in 1977. The DES, along with a large number of cryptosystems inspired by it, survived attempts at attack for several years. However, differential cryptanalysis has been used in recent years to effectively attack these systems. In addition to DES, differential cryptanalysis has exposed design flaws in many other iterated cryptosystems, showing that the time required to defeat some encryption techniques can by reduced to a matter of minutes, or even seconds, on personal computers. Although the DES itself appears relatively secure at this time, the revelation of exploitable weaknesses increases the need for alternative cryptosystems.
One drawback of iterated cryptosystems is the extreme difficulty associated with proving their security. One way to avoid this problem is to develop a cryptosystem that works from a strong foundation. The one-time pad is an example of such a cryptosystem. The one-time pad is the only cryptosystem which can be proven to be fully secure. However, in light of the severe requirements necessary to guarantee security, the one-time pad is not practical for general use.
Specifically, the one time pad requires, for any plaintext message M composed of i bits, a unique and random string K as the keyspace. Encryption of the plaintext messages is achieved by combining the plaintext message string and the random string by some bitwise mechanism, for example, the ciphertext C can be defined as the exclusive-or (XOR) product of M and K.
Applying the XOR operation, M and K are first converted into binary code. The binary codes representing M and K are then XORed bit by bit until the complete binary code of the ciphertext is produced. The ciphertext can then be converted to the plaintext message by XORing the ciphertext and the key.
The XOR operation, denoted , is completely defined by the following set of rules: 0 0=0;0 1=1:1 0=1;1 1=0. According to these rules, a second application of the XOR operation will reproduce the original number. This is the key feature permitting conversion of M to C and back to M based upon K.
Ideally, the distribution of the random string K is uniform and independent of the distribution of M, which implies that the distribution of C is uniform and independent of the distribution of M as well. Since K is random, any attempt to decrypt C, without knowledge of K, has only a minimal chance of success.
As mentioned above, proper application of the one-time pad entails requirements which greatly limit its practicality. First, the one-time pad requires the secure distribution of as much key material as plaintext. Second, a new random string must be used for each encryption, as attacks employing multiple ciphertexts encrypted under the same key are trivial. The impracticalities associated with these two requirements are referred to as the key management problem. Effective use of the one-time pad as a foundation for a new cryptosystem requires the elimination of the key management problem. Elimination of the key management problem can be accomplished if the amount of information needed to drive the cryptosystem is significantly decreased, without diminishing the scheme's security.
Development of a secure cryptosystem further requires effective and secure random number generation. Some of the more popular random number generators in use today are based on the linear congruential method, the middle square method, multiplicative methods, and mixed methods. These are enhanced by additional techniques such as data perturbation, swapping random sample queries, cell suppression, partitioning, and complex bitwise manipulation. These methods have met with varying degrees of success in different applications, but they do not provide a definitive answer to random number generation problems.
An ideal generator would produce a truly random sequence. However, this is impossible since the generation and analysis of a truly random sequence are not feasible in finite time. An actual generator can, therefore, produce only a pseudo random sequence for which various measures of randomness can be defined. For practical use in a given application, a pseudo random number (PRN) generator should desirably possess: (i) reproducibility, (ii) computational efficiency, and (iii) adherence to standards related to that specific application.
For instance, consider the computational efficiency of a PRN generator. The generator must be both rapid in the production of a pseudo random sequence and economical in its storage. In some cases, there is a direct trade-off between the two qualities. A routine designed to generate numbers to dynamically encrypt real time transfer of data is more concerned with the speed at which it can generate a pseudo random sequence. A routine intended to generate PRNs for the encryption of electronic documents, which are then stored, must incorporate efficient storage considerations. A configuration which possesses the maximum utility for a particular application must, therefore, be determined based upon the requirements of the particular application.
When employed within cryptographic applications, the PRN generator may come under the scrutiny of a well informed enemy, equipped with modern computational resources. The enemy's goal is to reproduce a particular sequence of pseudo random values. The enemy does not possess the unique initial information (i.e. initial values, seeds, and other variable parameters) associated with the sequence he wishes to regenerate. For the generator to be useful cryptographically, any attempt by the enemy to reproduce subsequent portions of a pseudo random sequence, given a finite portion of that sequence (referred to as an attack), must have a trivial chance of success in any useful amount of time.
To insure security against cryptographical attacks, a purely statistical notion of randomness must be avoided and a more cryptographically oriented definition must be adopted. Any statistical benefits incurred from a particular PRN generator which are not directly associated with its adherence to a cryptographic definition of randomness are cosmetic, and add little to the generator's usefulness. A cryptographically strong pseudo random number generator (CSPRING) must produce sequences of values which: (i) possess minimal internal correlation, (ii) convey minimal critical information regarding their origin, and (iii) are absolutely dependent upon unique and sensitive initial conditions for proper reproduction.
Minimal internal correlation requires that a sequence of PRNs must possess an acceptably small correlation between subsequent values and close neighbors. Furthermore, long range correlations (periodicity) are equally undesirable since the existence of such correlations can offer information regarding the nature of the CSPRING used to produce the sequence.
The critical information content of the sequences generated by a CSPRING must be carefully monitored. Critical information content is the quality of a sequence that associates it with the composition of a particular PRN generator and the specific parameters it employs. Output which retains critical information may be easily attributed to a particular PRN generator. Similarly, an output which retains minimal critical information can not practically be associated with any one particular method of PRN generation. For example, any member of an unaltered sequence of iterates resulting from some recursive process retains all the critical information necessary to recreate that sequence in either direction. In this sense, the critical information content of a sequence is directly related to the degree of internal correlation between its members. One method of visualizing the critical information content of a sequence is through the use of Poincare plots, which display a member of a sequence, x.sub.n+i, versus another member, x.sub.n. Depending upon the underlying dynamics of the PRN generator and the value of the lag i, such a plot may eventually reveal a structure which is directly dependent upon the critical information content of the sequence. Ideally, the PRN sequence used for cryptographic purposes does not reveal any such patterns.
A CSPRING must also demonstrate unique initial conditions for the generation of a pseudo random sequence, and sensitivity to any changes in those conditions. Ideally, each initial condition should eventually yield a unique pseudo random sequence, and no correlation should exist between two initial values and the similarity of the output they generate. In a realistic application, however, we do not exclude the possibility that the number of such initial conditions is relatively small.
Although many advances have been made in the science of cryptography, it is apparent that a need continues to exist for the fast and secure transmission of information. The present invention provides such a system.